<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>手写数组转树</title>
  </head>
  <body>
    <script>
      const arr = [
        { id: 1, name: "部门A", parentId: 0 },
        { id: 2, name: "部门B", parentId: 1 },
        { id: 3, name: "部门C", parentId: 1 },
        { id: 4, name: "部门D", parentId: 2 },
        { id: 5, name: "部门E", parentId: 2 },
        { id: 6, name: "部门F", parentId: 3 },
      ];

      //   function arrayToTree(arr, parentId = 0, parentKey = "parentId") {
      //     // 获取当前层的节点
      //     const list = arr.filter((item) => {
      //       return item[parentKey] === parentId;
      //     });
      //     // console.log("list", list);
      //     const filterList = list.map((item) => {
      //       return {
      //         ...item,
      //         children: arrayToTree(arr, item.id, parentKey),
      //       };
      //     });
      //     debugger;
      //     console.log("filterList", filterList);
      //     return filterList;
      //   }
      // 递归方式
      //   function arrayToTree(arr, parentId, parentKey = "parentId") {
      //     const result = [];
      //     for (const item of arr) {
      //       if (item.parentId === parentId) {
      //         const node = {
      //           ...item,
      //           children: arrayToTree(arr, item.id, parentKey),
      //         };
      //         result.push(node);
      //       }
      //     }
      //     return result;
      //   }

      //   const res = arrayToTree(arr, 0, "parentId");
      //   console.log("res", res);
      /*      // 执行顺序（深入）：
arrayToTree(0) → 处理id=1 → arrayToTree(1)
               → 处理id=2 → arrayToTree(2)
                          → 处理id=4 → arrayToTree(4) → 无子节点
                          → 处理id=5 → arrayToTree(5) → 无子节点
               → 处理id=3 → arrayToTree(3)
                          → 处理id=6 → arrayToTree(6) → 无子节点

// 返回顺序（回溯）：
arrayToTree(4)返回[] → id=4完成
arrayToTree(5)返回[] → id=5完成
→ arrayToTree(2)返回[id4,id5] → id=2完成
arrayToTree(6)返回[] → id=6完成
→ arrayToTree(3)返回[id6] → id=3完成
→ arrayToTree(1)返回[id2,id3] → id=1完成
→ arrayToTree(0)返回[id1] */

      // 不用递归
      function useMaparrToTree(arr) {
        // 用于作id和treeNode的映射
        const idToTreeNode = new Map();
        let root = null;
        arr.forEach((item) => {
          const { id, name, parentId } = item;
          // 定义tree node并加入map
          const treeNode = { id, name };
          idToTreeNode.set(id, treeNode);
          //   console.log("idTote", idToTreeNode);
          // 找到parentNode并加入到它们的children
          const parentNode = idToTreeNode.get(parentId);
          console.log("parentNode", parentNode);
          if (parentNode) {
            if (parentNode.children == null) {
              parentNode.children = [];
            }
            parentNode.children.push(treeNode);
          }
          // 找到根节点
          if (parentId === 0) {
            root = treeNode;
          }
        });
        return root;
      }
      function arr2tree(arr) {
        // 用于 id 和 treeNode 的映射
        const idToTreeNode = new Map();

        let root = null; // 返回一棵树 tree rootNode

        arr.forEach((item) => {
          const { id, name, parentId } = item;

          // 定义 tree node 并加入 map
          const treeNode = { id, name };
          idToTreeNode.set(id, treeNode);

          // 找到 parentNode 并加入到它的 children
          const parentNode = idToTreeNode.get(parentId);
          if (parentNode) {
            if (parentNode.children == null) {
              parentNode.children = [];
            }
            parentNode.children.push(treeNode); // 把treeNode加入到parentNode下
          }

          // 找到根节点
          if (parentId === 0) {
            root = treeNode;
          }
        });

        return root;
      }
      const res = useMaparrToTree(arr);
      console.log("res", res);
    </script>
  </body>
</html>
